/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */
 function hasPath( matrix ,  word ) {
  // write code here
  // 先记录一下 矩阵的长宽
  var m = matrix.length
  var n = matrix[0].length
  // 定义一下dfs的过程 深度优先搜索
  // 我们需要的参数有 当前是字符串当中的第几个字符,是矩阵当中的那一个格子 
  function dfs(k,i,j){
    // 如果这个位置不在矩阵格子范围当中 0<i<m 0<j<n 或者 当前字符串中的字符和格子中的字符并不相等
    if(i < 0 || i >= m || j < 0 || j >= n || word[k] !== matrix[i][j]){
      // 那么我直接就返回 false
      return false
    }else{
      // 这种情况就是 这个k位的字符和数组中的字符相等 
      // 判断这个字符是不是最后一个字符 
      if(k === word.length-1){
        // 如果是的话 说明取到了字符串的末尾 就是矩阵中确实有题目要求的路径
        return true
      }else{
        // 这个时候是已经找到k这个字符了
        // 路径不允许进入同一个格子多次的 1.建立一个和矩阵同样大小的数组 记录为visited 他用来记录在当前找到路径当中坐标为ij的格子是不是被访问过 这样的开销比较大 
        // 2. 我们先记录一下当前格子的内容
        var temp = matrix[i][j]
        // 把格子的内容修改成一个不可能被访问到的字符
        matrix[i][j] = '#'
        // 这样就避免了重复的路径
        // 如果k不是最后一个下标 那需要判断下一个位置的字符 那我们就需要检查一个各个方向 看看是不是有继续走下去的路径
        res = dfs(k+1,i-1,j) || dfs(k+1,i+1,j) || dfs(k+1,i,j-1) || dfs(k+1,i,j+1)
        // 最后各个方向都尝试了之后 将其恢复到原来的内容
        matrix[i][j] = temp
        // 最后返回结果
        return res
      }
    }
  }
  // 题目中说 路径是可以从矩阵的任意一个开始的
  // 所以遍历这个矩阵的格子
  // 从每一个格子开始出发
  for(var i = 0;i < m;i++){
    for(var j = 0;j < n;j++){
      // 从每一个格子开始出发
      if(dfs(0,i,j)){
        return true
      }
    }
  }
  return false
}
module.exports = {
  hasPath : hasPath
};
